1063D - Candies for Children - CodeForces Solution

#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

#define madd(x, y, m) (((x) + (((y) + (m)) % (m))) % (m))



constexpr int INF = (int) 1e9 + 7;

constexpr int MAXN = (int) 1e6 + 5;

constexpr int MOD = 998244353;



int dx[] = {-1, 0, 1, 0};

int dy[] = {0, -1, 0, 1};



ll n, l, r, k;

bool read() {

    cin >> n >> l >> r >> k;

    return cin.good();

}



bool solve() {





    r = l <= r ? r - l + 1 : n - l + r + 1;

    ll suf = n - r;



    if (k < r) {

        cout << -1;

    } else if (k - r <= r) {

        cout << min(n, suf + k - r + 1);

    } else if (n < MAXN) {

        ll x = n;

        while (x >= 0) {

            ll y = (k - r) % (n + x);

            if (y <= r && y >= x - suf - 1) {

                break;

            }

            --x;

        }

        cout << x;

    } else {

        ll a = 1;

        ll C = k - r - n;

        while (C >= 0) {

            ll x = (C + suf + 1) / (a + 1);

            ll y = C - a * x;

            assert(y >= x - suf - 1);

            if (y <= r) {

                cout << x;

                return true;

            }

            C -= n;

            a++;

        }

        cout << -1;

    }



    return true;

}



void init() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    // freopen("output.txt", "w", stdout);

#endif



    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    cout << fixed << setprecision(7);

}



int32_t main() {

    auto begin = chrono::steady_clock::now();

    init();

    while (read()) {

        solve();

//    cout << (solve() ? "YES" : "NO");

        cout << endl;

    }

    auto end = chrono::steady_clock::now();

    cerr << "Elapsed time (ms): " << chrono::duration_cast<chrono::milliseconds>(end - begin).count();

    return 0;

}